Khung toán học
Mục tiêu cốt lõi là tìm một vectơ $x \in \mathbb{R}^n$ sao cho tổ hợp tuyến tính $Ax = x_1a_1 + \dots + x_na_n$ xấp xỉ tốt nhất với $b$. Điều này thường được gọi là phép hồi quy của $b$ lên các biến độc lập (các cột của ma trận $A$).
Chúng ta tập trung vào vectơ dư $r = Ax - b$. Trong thực tế, ta thường giả sử một hệ thống hệ quá xác định trong đó $m > n$. Tại sao? Vì khi $m = n$ và ma trận $A$ khả nghịch, điểm tối ưu đơn giản là $A^{-1}b$, dẫn đến sai số bằng không – một trường hợp tầm thường trong tối ưu hóa.
Các dạng chuẩn
Tùy theo loại sai số mà chúng ta muốn trừng phạt, ta chọn các chuẩn khác nhau:
Phương pháp phổ biến nhất. Nó cực tiểu hóa tổng bình phương các sai số dư: $\|Ax - b\|_2^2$. Phương pháp này nhạy cảm với các giá trị ngoại lai lớn nhưng lại mang lại lời giải chính xác thông qua các phương trình bình phương.
Cực tiểu hóa giá trị cực đại tuyệt đối $\max_i |r_i|$. Phương pháp này được dùng khi mỗi phép đo đều phải nằm trong giới hạn nghiêm ngặt. Bài toán có thể được giải bằng chương trình tuyến tính (LP) sau:
cực tiểu hóa $t$
với điều kiện $-t\mathbf{1} \preceq Ax - b \preceq t\mathbf{1}$
Cực tiểu hóa $\sum |r_i|$. Phương pháp này bền vững trước các giá trị ngoại lai vì nó không bình phương sai số. Đồng thời, bài toán cũng có thể giải được thông qua chương trình tuyến tính (LP):
cực tiểu hóa $\mathbf{1}^T t$
với điều kiện $-t \preceq Ax - b \preceq t$
Bối cảnh ước lượng
Trong nhiều lĩnh vực kỹ thuật, ta giả sử trạng thái thực $x$ bị che khuất bởi nhiễu: $y = Ax + v$. Mục tiêu của ta là tìm ước lượng $\hat{x} = \text{argmin}_z \|Az - y\|$. Việc chọn chuẩn tương ứng chính là việc đưa ra giả định về phân phối thống kê của nhiễu $v$.